package com.test.daily.leetcode.y2021.m10.day1016;

import java.util.ArrayList;
import java.util.List;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2021/10/16 上午 09:43
 * @version: 1.0
 */
public class Code01_Merge {
    int n;
    String num;
    int target;
    List<String> ans;

    public static void main(String[] args) {
        Code01_Merge cm = new Code01_Merge();
        String num = "123";
        int target = 2;
        List<String> list = cm.addOperators(num, target);
//        list.forEach(ele -> System.out.println(ele));

    }

    public List<String> addOperators(String num, int target) {
        this.n = num.length();
        this.num = num;
        this.target = target;
        this.ans = new ArrayList<String>();
        StringBuffer expr = new StringBuffer();
        backtrack(expr, 0, 0, 0);
        return ans;
    }

    /**
     * @param expr 已经生成的表达式
     * @param i    当前已经来到了i位置
     * @param res  前面的结果
     * @param mul  回溯的数值，当最后的字符选择乘号，需要回溯
     */
    public void backtrack(StringBuffer expr, int i, long res, long mul) {
        if (i == n) {
            if (res == target) {
                System.out.println(expr.toString());
                ans.add(expr.toString());
            }
            return;
        }
        int signIndex = expr.length();
        if (i > 0) {
            // 占位, 下面填充符号
            expr.append(0);
        }
        long val = 0;
        // 枚举截取的数字长度(取多少位)，注意数字可以是单个0，但是不能有前导0
        // j来到了第一位后面的数字，但是以i开头，j结尾的数字，不能包含类似0111这种
        for (int j = i; j < n && (j == i || num.charAt(i) != '0'); ++j) {
            val = val * 10 + num.charAt(j) - '0';
            expr.append(num.charAt(j));
            if (i == 0) {
                backtrack(expr, j + 1, val, val);
            } else {
                expr.setCharAt(signIndex, '+');
                backtrack(expr, j + 1, res + val, val);
                expr.setCharAt(signIndex, '-');
                backtrack(expr, j + 1, res - val, -val);
                expr.setCharAt(signIndex, '*');
                backtrack(expr, j + 1, res - mul + mul * val, mul * val);
            }
        }
        // 恢复现场？
        expr.setLength(signIndex);
    }
}
